package com.lry.basic.algorithm.common;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 输入：[1,7,5,1,9,10,5,1]
 * 输出：[7,9,9,9,10,0,0,0]
 */
public class NextLargerNum {

    public int[] nextLargerNum(int[] nums) {
        if(null==nums||nums.length==0)
            return new int[0];
        int[] dp = new int[nums.length];

        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                dp[i] = nums[i+1];
            }else if(nums[i]==nums[i+1]){
                dp[i] = dp[i+1];
            }else{
                int min = 0;
                for(int j=i+1;j<dp.length;j++){
                    if(dp[j]>nums[i]){
                        min = dp[j];
                        break;
                    }else if(dp[j]==0){
                        break;
                    }
                }
                dp[i] = min;
            }
        }
        return dp;
    }

    //1，3，2，4
    public int[] nextLargerNum2(int[] nums) {
        if(null==nums||nums.length==0)return new int[0];
        Stack<Integer> stack = new Stack();

        for(int i=0;i<nums.length;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                nums[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            nums[stack.pop()] = 0;
        }
        return nums;
    }

    //1，3，2，4
    public int[] nextLargerNum22(int[] nums) {
        if(null==nums||nums.length==0)return new int[0];
        int[] ans = new int[nums.length];
        Stack<Integer> stack = new Stack();//单调栈 单调不减

        for(int i=nums.length-1;i>=0;--i){
            while(!stack.isEmpty()&&nums[stack.peek()]<=nums[i]){
                stack.pop();
            }
            ans[i] = stack.isEmpty()?0:nums[stack.peek()];
            stack.push(i);
        }

        return ans;
    }






//    给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
//    数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，
//    这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
//
//    示例 1:
//    输入: [1,2,1]
//    输出: [2,-1,2]

    public int[] nextLargerNum3(int[] nums) {
        int[] res = new int[nums.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 2 * nums.length - 1; i >= 0; --i) {

            while (!stack.empty() && nums[stack.peek()] <= nums[i % nums.length]) {
                stack.pop();
            }

            res[i % nums.length] = stack.empty() ? -1 : nums[stack.peek()];

            stack.push(i % nums.length);
        }

        return res;

    }


//    给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
//    nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if(null==nums1||nums1.length==0||null==nums2||nums2.length==0)return new int[0];
        Stack<Integer> stack = new Stack();
        Map<Integer,Integer> map  = new HashMap();

        for(int i=0;i<nums2.length;i++){
            while(!stack.isEmpty()&&stack.peek()<nums2[i]){
                map.put(stack.pop(),nums2[i]);
            }
            stack.push(nums2[i]);
        }

        while(!stack.isEmpty()){
            map.put(stack.pop(),-1);
        }
        for(int i=0;i<nums1.length;i++){
            nums1[i] = map.get(nums1[i]);
        }

        return nums1;
    }


    public static void main(String[] args) {
        int[] res = new NextLargerNum().nextLargerNum(new int[]{1,7,5,1,9,10,5,1});
        for(int r:res){
            System.out.print(r+" ");
        }
        System.out.println();
        res = new NextLargerNum().nextLargerNum22(new int[]{1,7,5,1,9,10,5,1});
        for(int r:res){
            System.out.print(r+" ");
        }
        System.out.println();
        res = new NextLargerNum().nextLargerNum3(new int[]{1,7,5,1,9,10,5,1});
        for(int r:res){
            System.out.print(r+" ");
        }

    }
}
